﻿#define  _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
#include"Stack.h"

//直接插入排序
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else {
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

//希尔排序
//void ShellSort(int* arr, int n)
//{
//	int gap = n;
//	while (gap > 1)
//	{
//		gap = gap / 3 + 1;
//		for (int i = 0; i < gap; i++)
//		{
//			for (int i = 0; i < n - gap; i += gap)
//			{
//				int end = i;
//				int tmp = arr[end + gap];
//				while (end >= 0)
//				{
//					if (arr[end] > tmp)
//					{
//						arr[end + gap] = arr[end];
//						end -= gap;
//					}
//					else {
//						break;
//					}
//				}
//				arr[end + gap] = tmp;
//			}
//		}
//	}
//}

//优化
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else {
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//向下调整算法 logn
void AdjustDown(int* arr, int parent, int n)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//建大堆：<
		//建小堆: >
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		//孩子和父亲比较
		//建大堆：>
		//建小堆:<
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

//堆排序————使用的是堆结构的思想 n * logn
void HeapSort(int* arr, int n)
{
	//向下调整算法——建堆n
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}

	////向上调整算法建堆n*logn
	//for (int i = 0; i < n; i++)
	//{
	//	AdjustUp(arr, i);
	//}

	//n*logn
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);//logn
		end--;
	}
}

//冒泡排序
//void BubbleSort(int* arr, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < n - i - 1; j++)
//		{
//			if (arr[j] > arr[j + 1])
//			{
//				Swap(&arr[j], &arr[j + 1]);
//			}
//		}
//	}
//}
//优化冒泡排序
void BubbleSort(int* a, int n)
{
	int exchange = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				exchange = 1;
				Swap(&a[j], &a[j + 1]);
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}
//
////直接选择排序
//void SelectSort(int* arr, int n)
//{
//	int begin = 0, end = n - 1;
//	while (begin < end)
//	{
//		int mini = begin;
//		int maxi = begin;
//		for (int i = begin + 1; i <= end; i++)
//		{
//			if (arr[i] < arr[mini])
//			{
//				mini = i;
//			}
//			if (arr[i] > arr[maxi])
//			{
//				maxi = i;
//			}
//		}
//		
//		Swap(&arr[begin], &arr[mini]);
//		Swap(&arr[end], &arr[maxi]);
//
//		begin++;
//		end--;
//	}
//}

//直接选择排序 n^2
void SelectSort(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&arr[begin], &arr[mini]);
		Swap(&arr[end], &arr[maxi]);

		begin++;
		end--;
	}
}

////找基准值 hoare版本
//int _QuickSort(int* arr, int left, int right)
//{
//	int keyi = left;
//	left++;
//	while (left <= right)
//	{
//		//right:从右往左走，找比基准值小的数
//		while(left <= right && arr[right] > arr[keyi])
//		{
//			--right;
//		}
//		//left:从左往右走，找比基准值大的数
//		while (left <= right && arr[left] < arr[keyi])
//		{
//			++left;
//		}
//		//left right交换
//		if (left <= right)
//			Swap(&arr[left++], &arr[right--]);
//	}
//	//right的位置就是基准值
//	Swap(&arr[keyi], &arr[right]);
//	return right;
//}

////找基准值 挖坑法
//int _QuickSort(int* arr, int left, int right)
//{
//	int hole = left;
//	int key = arr[hole];
//	while (left < right)
//	{
//		while (left < right && arr[right] > key)
//		{
//			right--;
//		}
//		arr[hole] = arr[right];
//		hole = right;
//
//		while (left < right && arr[left] < key)
//		{
//			++left;
//		}
//		arr[hole] = arr[left];
//		hole = left;
//	}
//	arr[hole] = key;
//	return hole;
//}

//找基准值 lomuto前后指针
int _QuickSort(int* arr, int left, int right)
{
	int prev = left, cur = prev + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		++cur;
	}
	Swap(&arr[keyi], &arr[prev]);
	return prev;
}

//快速排序
void QuickSort(int* a, int left, int right)
{
	if (left >= right) {
		return;
	}
	//_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分 
	//找基准值
	int keyi = _QuickSort(a, left, right);
	//左序列[left,keyi]，右序列[keyi,right]
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

void _QuickSortArray(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left;
	int end = right;

	//随机选key
	int randi = left + (rand() % (right - left + 1));
	Swap(&a[left], &a[randi]);

	int key = a[left];
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < key)
		{
			Swap(&a[cur], &a[left]);
			++left;
			++cur;
		}
		else if (a[cur] > key)
		{
			Swap(&a[cur], &a[right]);
			--right;
		}
		else
		{
			++cur;
		}
	}
	//[begin,left-1] [left,right] [right+1,end]
	_QuickSortArray(a, begin, left - 1);
	_QuickSortArray(a, right + 1, end);
}

//快速排序--三路划分
int* sortArray(int* nums, int numsSize) //numsSize是数组的大小不是下标 
{
	srand(time(0));
	_QuickSortArray(nums, 0, numsSize - 1);
	//*returnSize = numsSize; 排序不需要输出型参数  
	return nums;
}

void _IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{
	if (left >= right)
	{
		return;
	}
	//数组长度小于16的小数组，换为插入排序，简单递归次数
	if (right - left + 1 < 16)
	{
		InsertSort(a + left, right - left + 1);
		return;
	}
	//当深度超过2logN，则改用堆排序
	if (depth > defaultDepth)
	{
		HeapSort(a + left, right - left + 1);
		return;
	}
	depth++;
	
	int begin = left;
	int end = right;
	//随机选key
	int randi = left + (rand() % (right - left));
	Swap(&a[left], &a[randi]);

	int prev = left;
	int cur = prev + 1;

	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
		
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	// [begin, keyi-i] keyi [keyi+l, end]
	_IntroSort(a, begin, keyi - 1, depth, defaultDepth);
	_IntroSort(a, keyi + 1, end, depth, defaultDepth);
}
	
//快排--自省排序
void IntroSort(int* a, int left, int right)
{
	int depth = 0;
	int logn = 0;

	int n = right - left + 1;
	for (int i = 1; i < n; i *= 2)
	{
		logn++;
	}
	//introspectivesort--自省排序
	_IntroSort(a,left, right, depth, logn * 2);
}

//非递归版本---借助栈
void QuickSortNorR(int* arr, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);
	while (!STEmpty(& st))
	{
		//取栈顶两次
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);
		//[begin,end]找基准值
		int keyi = begin;
		int prev = begin, cur = prev + 1;
		while (cur <= end)
		{
			if (arr[cur] < arr[keyi] && ++prev != cur)
			{
				Swap(&arr[prev], &arr[cur]);
			}
			++cur;
		}
		Swap(&arr[prev], &arr[keyi]);
		keyi = prev;
		//begin keyi end
		//左序列[begin,keyi - 1]
		//右序列[keyi + 1,end]
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}
		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st,begin);
		}
	}
	STDesTroy(&st);
}

//归并排序--递归
void _MergeSort(int* arr, int left, int right, int* tmp)
{
	//分解
	if (left >= right)//这样更保险，==也可以
	{
		return;
	}
	int mid = (left + right) / 2;
	//mid将[left,right]划分左右两个序列:[left,mid] [mid+1,right]
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	//合并两个序列:[left,mid] [mid,right]
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else {
			tmp[index++] = arr[begin2++];
		}
	}
	//分类讨论begin1和begin2
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}
	//返给arr
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}

//归并排序
void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	//[0,n-1]
	_MergeSort(arr, 0, n - 1, tmp);
	free(tmp);
}

//归并排序--非递归
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail\n");
		exit(1);
	}
	int gap = 1;
	while (gap < n)
	{
		//根据gap划分组，两两合并
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			if (begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			int index = begin1;
			//两个有序序列进行合并
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[index++] = a[begin1++];
				}
				else {
					tmp[index++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
			//导入到原数组
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
}

//非比较排序——计数排序
void CountSort(int* arr, int n)
{
	//找min max
	int min = arr[0], max = arr[0];
	for (int i = 1; i < n; i++)
	{
		if (arr[i] < min)
		{
			min = arr[i];
		}
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	//确定count数组的大小 max-min+1
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * (range));
	if (count == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	//对count初始化：calloc memset
	memset(count, 0, sizeof(int) * (range));
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}
	//将count数组中的数据还原到原数组中
	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[index++] = i + min;
		}
	}
}